import java.util.HashSet;
import java.util.Set;

public class Test {
}
class Solution {
    /**
     解决怎么装背包时，能装最多的物品
     1. i：有多少0
     j: 有多少1
     dp[i][j]: 最多能装多少物品
     dp[i][j] = Math.max(dp[i][j],dp[i-x][j-y]+1);
     */
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for(String s : strs){
            int x = 0, y = 0;
            for(char c : s.toCharArray()){
                if(c == '0') x++;
                else y++;
            }
            for(int i=m; i>=x; i--){
                for(int j=n; j>=y; j--){
                    dp[i][j] = Math.max(dp[i][j],dp[i-x][j-y]+1);
                }
            }
        }
        return dp[m][n];
    }
}
class Solution1 {
    long[][] memo = new long[8001][2];//记忆化
    boolean[][] visited = new boolean[8001][2];//[数轴位置][连续向后位移次数]
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        Set<Integer> set = new HashSet<>();
        for(int y : forbidden){
            set.add(y);
        }
        long ans = dfs(0,set,a,b,x,0);
        if(ans == Integer.MAX_VALUE) return -1;
        return (int)ans;
    }
    long dfs(int cur, Set<Integer> set, int a, int b, int x, int backCount){
        if(memo[cur][backCount]!=0)
            return memo[cur][backCount];
        if(cur == x)
            return 0;
        visited[cur][backCount] = true;
        long res = Integer.MAX_VALUE;
        if(cur+a<=8000 && !set.contains(cur+a) && !visited[cur+a][0])//想前移动，最后一个条件是为了防止重复递归
            res = Math.min(res,1+dfs(cur+a,set,a,b,x,0));
        if(cur-b>=0 && backCount<1 && !set.contains(cur-b) && !visited[cur-b][backCount+1])//向后移动
            res = Math.min(res,1+dfs(cur-b,set,a,b,x,backCount+1));
        return memo[cur][backCount] = res;
    }
}